/**
 * 106. 从中序与后序遍历序列构造二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 */
public class Solutions_106 {
    public static void main(String[] args) {
        int[] inorder = {9, 3, 15, 20, 7};  // 中序遍历
        int[] postorder = {9, 15, 7, 20, 3};  // 后序遍历
        // output: {3, 9, 20, null, null, 15, 7}

//        int[] inorder = {1, 2, 3};  // 中序遍历
//        int[] postorder = {1, 3, 2};  // 后序遍历
        // output: {2, 1, 3}

        TreeNode result = buildTree(inorder, postorder);
        System.out.println(result);
    }

    // 记录中序与后序的索引
    private static int in;
    private static int post;

    /**
     * 先序遍历：根左右
     * 中序遍历：左根右
     * 后序遍历：左右根
     */
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        in = inorder.length - 1;
        post = postorder.length - 1;
        return buildTree(inorder, postorder, Integer.MAX_VALUE);
    }

    public static TreeNode buildTree(int[] inorder, int[] postorder, int stop) {
        if (post < 0) {
            // 结束条件：左子树构造完成
            return null;
        }
        if (inorder[in] == stop) {
            in --;
            return null;
        }
        // 创建根节点，节点值即是 postorder 的末尾元素
        int curVal = postorder[post--];
        // 每个节点都是根节点，遍历完成左右子树的构造
        TreeNode cur = new TreeNode(curVal);
        // 后序遍历为左右根，而 postorder 中是倒序取值的，故先填充右子树，再填充左子树
        // 在 inorder 中，位于 curVal 后面的元素，都是 curVal 的右子树节点
        // 根据以上推理，可以得到，倒序遍历 inorder 时，遇到 curVal 根节点，说明右子树构造完成
        cur.right = buildTree(inorder, postorder, curVal);
        // 在 inorder 中，位于 curVal 前面的元素，都是 curVal 的左子树节点
        // 根据以上推理，可以得到，倒序遍历 inorder 时，遇到祖父节点 stop
        // 在中序遍历中，一个左子节点的前一元素是父节点的父节点
        // 或者 in 小于 0 时说明左子树构造完成
        cur.left = buildTree(inorder, postorder, stop);
        return cur;
    }
}
